#!/usr/bin/env python
# -*- coding:utf-8 -*-
# @Author  : 邢建辉
# @Email   : xjh_0125@sina.com
# @Time    : 2022/8/15 17:38
# @Software: PyCharm
# @File    : l1130mct_leaf_values.py


class Solution:
    def mctFromLeafValues(self, arr: list[int]) -> int:
        if len(arr) <= 1:
            return arr[0]
        c = len(arr)
        dp = [[0 * i for i in range(len(arr))] for j in range(len(arr))]
        dp[0][0] = arr[0]
        dp[0][1] = arr[1] * arr[0]
        for i in range(2, c):
            dp[0][i] = dp[0][i - 1] + max(arr[0:i - 1]) * arr[i]
        print(dp)
        for i in range(1, c):
            for j in range(1, c):
                dp[i][j] = max(arr[0:j]) * max(arr[j:c]) + dp[i][j - 1] + dp[j][c - 1]
        print(dp)
        return dp[c - 1][c - 1]


if __name__ == '__main__':
    s = Solution()
    arr = [6, 2, 4, 6]
    res = s.mctFromLeafValues(arr)
    print(res)
